package main

import "fmt"

// 位运算

// 异或运算又称为无进位相加
// 0 ^ n = n
// n ^ n = 0
// a ^ b = b ^ a
// a ^ b ^ c = a ^ (b ^ c)

// ~a + 1 = -a

// 取出一个数最右侧的1
// a & (~a + 1) || a & (-a)

func Swap(a, b int) (int, int) {
	a = a ^ b
	b = a ^ b
	a = a ^ b
	return a, b
}

func xor(arr []int) int {
	eor := 0
	for _, i := range arr {
		eor = eor ^ i
	}
	return eor
}

// 两个不同的数 a,b 出现了奇数次 其他数出现了偶数次，找出a，b
func findOddNumber(arr []int) (int, int) {
	eor := 0
	for _, i := range arr {
		eor = eor ^ i
	}
	// 此时eor = a ^ b
	// a ^ b 必定不等于0， 且 a与b必定有一位不相等 0，1
	// 取出一个数最右侧的1
	eor1 := eor & (^eor + 1)
	var a int = 0
	for _, i := range arr {
		if i&eor1 != 0 {
			a = a ^ i
		}
	}
	b := a ^ eor
	return a, b
}

// 只有一个数出现了k次，其他数出现了m次 && m>1 && m>k 找到K对应的数
func search(arr []int32, k, m int32) int32 {
	var a []int32 = make([]int32, 32)

	// 将数据内所有二进制每一位想加
	for i := 0; i < len(arr); i++ {
		for j := 0; j < 32; j++ {
			// (arr[i] >> j) & 1 取出第j位的二进制数
			a[j] += (arr[i] >> j) & 1
		}
	}

	var ans int32 = 0
	for i := 0; i < len(a); i++ {
		// a[i] % m == 0 说明此二进制位置 只有 M 对应的数有值
		if a[i]%m != 0 {
			// 说明二进制该位置K对应的数，有值
			ans += 1 << i
		}
	}

	return ans
}

func main() {
	//a := 1
	//b := 2
	//a, b = Swap(a, b)
	//fmt.Println(a, b)

	//fmt.Println(xor([]int{1, 1, 2, 2, 2}))

	//fmt.Println(findOddNumber([]int{1, 1, 2, 2, 2, 5, 5, 5, 5, 7, 7, 7}))
	fmt.Println(search([]int32{1, 1, -1, -1, 1, 3, 3, 3, -1, 2}, 1, 3))
}
